#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
        std::sort(candidates.begin(), candidates.end());
        trace_back(candidates, 0, 0, target);
        return _ans;
    }

private:
    bool trace_back(const std::vector<int>& candidates, size_t start, int cur, int target)
    {
        if (cur == target) {
            _ans.emplace_back(_v);
            return false;
        }
        else if (cur > target) {
            return false;
        }

        for (size_t i = start; i < candidates.size(); ++i)
        {
            _v.emplace_back(candidates[i]);
            bool ret = trace_back(candidates, i, cur + candidates[i], target);
            _v.pop_back();

            if (!ret) {
                break;
            }
        }

        return true;
    }

    std::vector<int> _v;
    std::vector<std::vector<int>> _ans;
};